package com.nanbei.recursion;

import java.util.LinkedList;

/**
 * @ClassDescription: 多路递归
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/11/21 16:58
 */
public class MultiRecursion {

    public static int fibonacci(int x) {
        if (x == 0) {
            return 0;
        }
        if (x ==1) {
            return 1;
        }

        return fibonacci(x-1)+fibonacci(x-2);


    }

    /**
     * 多路递归-记忆法  将计算完成以后的数值用数组保存起来
     * @param index f(n) 中的n  也是该函数在数组的下标
     * @param nums  用来记录f(n)值 的数组
     * @return f(n) 的值
     */
    public static int fibonacci(int index , int[] nums) {
        if (nums[index] != 0){
            return nums[index];
        }

        nums[index] = fibonacci(index - 1, nums) + fibonacci(index - 2, nums);
        return  nums[index];

    }

}
